//给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 
//
// 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "bbbab"
//输出：4
//解释：一个可能的最长回文子序列为 "bbbb" 。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出：2
//解释：一个可能的最长回文子序列为 "bb" 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 825 👎 0


package leetcode.editor.cn;

/**
 * 最长回文子序列
 * @date 2022-07-05 13:52:15
 */
class P516_LongestPalindromicSubsequence{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P516_LongestPalindromicSubsequence().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestPalindromeSubseq(String s) {
		/**
		 *思路  dp[i][j]表示s[i..j]代表的字符串的最长回文子序列
		 * d[i][i]=1
		 * dp[i][j] = dp[i+1][j-1]+2 当s[i]=s[j]
		 * dp[i][j]=max(dp[i+1][j],dp[i][j-1])
		 * 当s[i]!=s[j] 取s[i+1..j] 和s[i..j-1]中最长的
		 * 由于dp[i][j]需要dp[i+1][j]所以需要逆序枚举s的长度，而又因为
		 * 在求解dp[i][j]时,dp[i][j-1]肯定已经求解过了,故j是递增的，
		 */
		int[][] dp = new int[s.length()][s.length()];
		//初始化
		for (int i = 0; i < s.length(); i++) {
			dp[i][i] = 1;
		}
		for (int i = s.length()-1; i >=0; i--) {
			for (int j = i+1; j < s.length(); j++) {
				if(s.charAt(i) == s.charAt(j)){
					dp[i][j] = dp[i+1][j-1] + 2;
				}else {
					dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
				}
			}
		}
		return dp[0][s.length()-1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
